from typing import List
INF = 10 ** 10


def solve(turn_limit, clear_limit, grids: List[List[str]]):
    n_rows = len(grids)
    n_cols = len(grids[0])
    s, t = None, None
    for i in range(n_rows):
        for j in range(n_cols):
            if grids[i][j] == 'S':
                s = (i, j)
            if grids[i][j] == 'T':
                t = (i, j)

    up, down, left, right, mid = 0, 1, 2, 3, 4
    def dir_to_str(direction):
        strs = ['up', 'down', 'left', 'right', 'mid']
        return strs[direction]

    def is_same_direction(d1, d2):
        return d1 == mid or d1 == d2

    def is_adv_direction(d1, d2):
        return sorted([d1, d2]) in [[0, 1], [2, 3]]

    def adj(coord):
        i, j, direction = coord
        if (i, j) in [s, t] and direction != mid:
                return []
        if (i, j) == t:
            return []

        adjs = []
        for to_direction, (i1, j1) in enumerate([(i-1, j), (i+1, j), (i, j-1), (i, j+1)]):
            if not (0 <= i1 < n_rows and 0 <= j1 < n_cols):
                continue
            if (i1, j1) == s:
                continue
            elif (i1, j1) == t:
                if is_same_direction(direction, to_direction):
                    adjs.append(((i1, j1, mid), 0))
                elif is_adv_direction(direction, to_direction):
                    continue
                else:
                    adjs.append(((i1, j1, mid), 1))
            else:
                if is_same_direction(direction, to_direction):
                    adjs.append(((i1, j1, to_direction), 0))
                elif is_adv_direction(direction, to_direction):
                    continue
                else:
                    adjs.append(((i1, j1, to_direction), 1))
        return adjs

    def dijkstra(s, t, d_limit, hop_limit, grids):
        import heapq
        d = {(i, j, direction): INF for i in range(n_rows) for j in range(n_cols) for direction in range(5)}
        hops = {(i, j, direction): INF for i in range(n_rows) for j in range(n_cols) for direction in range(5)}
        parents = {(i, j, direction): None for i in range(n_rows) for j in range(n_cols) for direction in range(5)}

        d[s] = 0
        hops[s] = 0
        q = [[d[s], 0, s]]
        while q:
            du, hu, u = heapq.heappop(q)
            print(du, hu, (u[0], u[1], dir_to_str(u[2])))
            if du > d[u] and hu > hops[u]:
                continue
            if u == t:
                return d, parents
            for v, w in adj(u):
                alt = d[u] + w
                extra_hop = int(grids[v[0]][v[1]] == '*')
                if alt < d[v] and alt <= d_limit and hu + extra_hop <= hop_limit:
                    parents[v] = u
                    d[v] = alt
                    hops[v] = hu + extra_hop
                    heapq.heappush(q, [d[v], hops[v], v])
        return d, parents

    distances, parents = dijkstra(s + (mid,), t + (mid,), turn_limit, clear_limit, grids)
    result = distances[t + (mid,)] < INF
    if result:
        path = []
        u = t + (mid,)
        while u != s + (mid,):
            path.append(u)
            u = parents[u]
        path.append(s + (mid,))
        path.reverse()
        print(path)
    return result



turn_limit = 2
clear_limit = 0
grids = """
..S..
****.
T....
****.
.....
""".strip().split('\n')
res = solve(turn_limit, clear_limit, grids)
print(res)


turn_limit = 2
clear_limit = 0
grids = """
..S..
****.
T..*.
****.
.....
""".strip().split('\n')
res = solve(turn_limit, clear_limit, grids)
print(res)


turn_limit = 2
clear_limit = 1
grids = """
..S..
****.
T..*.
****.
.....
""".strip().split('\n')
res = solve(turn_limit, clear_limit, grids)
print(res)


turn_limit = 2
clear_limit = 1
grids = """
..S..
****.
T.**.
****.
.....
""".strip().split('\n')
res = solve(turn_limit, clear_limit, grids)
print(res)


turn_limit = 4
clear_limit = 1
grids = """
..S..
****.
****.
**...
T.***
****.
****.
****.
.....
""".strip().split('\n')
res = solve(turn_limit, clear_limit, grids)
print(res)

